package subsetXORSum;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    int res=0;
    public int subsetXORSum(int[] nums) {
        LinkedList<Integer>list=new LinkedList<>();
        for (int i = 1; i <= nums.length; i++) {
            backTraking(0,i,nums,list);
        }
        return res;
    }
    private void backTraking(int startIndex, int k, int[]nums, LinkedList<Integer> list){
        if(list.size()==k){
            // 已经遍历完了
            int m=list.get(0);
            for (int i = 1; i < list.size(); i++) {
                m=m^list.get(i);
            }
            res+=m;
            return;
        }
        for (int i = startIndex; i <nums.length-(k-list.size())+1 ; i++) {
            list.add(nums[i]);
            backTraking(i+1,k,nums,list);
            list.removeLast();//回溯操作
        }
    }
}
// 异或 二进制中相同为0 不同为1
// 回溯算法